home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / prog / graph / short.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  2.1 KB  |  118 lines
  1. #include <LEDA/graph.h>
  2. #include <LEDA/graph_alg.h>
  3.  
  4.  
  5. main()
  6. {
  7.  
  8. GRAPH<int,int> G;
  9. node s,v,w;
  10. edge e;
  11.  
  12. int n = read_int("# nodes = ");
  13. int m = read_int("# edges = ");
  14.  
  15. random_graph(G,n,m);
  16.  
  17. edge_array<int>  cost1(G,0);
  18. node_array<int>  dist1(G,0);
  19. node_array<int>  dist2(G,0);
  20. node_array<edge> pred(G,nil);
  21.  
  22.  
  23. int a = read_int("a = ");
  24. int b = read_int("b = ");
  25.  
  26. forall_edges(e,G) cost1[e] = G[e] = random(a,b);
  27.  
  28. s = G.first_node();
  29.  
  30. float T = used_time();
  31.  
  32. cout << "DIJKSTRA <int>      ";
  33. cout.flush();
  34. DIJKSTRA(G,s,cost1,dist1,pred);
  35. cout << string("%6.2f sec  \n",used_time(T));
  36.  
  37. cout << "BELLMAN_FORD <int>  ";
  38. cout.flush();
  39. BELLMAN_FORD(G,s,cost1,dist2,pred);
  40. cout << string("%6.2f sec  \n",used_time(T));
  41.  
  42. if (Yes("output     ? "))
  43.  { forall_nodes(v,G)
  44.    { G.print_node(v);
  45.     cout << string(" %6d %6d\n",dist1[v],dist2[v]);
  46.     }
  47.    newline;
  48.   }
  49.  
  50.  
  51. if (Yes("all pairs shortest paths <int> ? "))
  52. { 
  53.   node_matrix<int> Mi(G);
  54.  
  55.   used_time(T);
  56.   cout << "ALL PAIRS SHORTEST PATHS <int> ";
  57.   cout.flush();
  58.   ALL_PAIRS_SHORTEST_PATHS(G,cost1,Mi);
  59.   cout << string("%.2f sec\n",used_time(T));
  60.   
  61.   if (Yes("output ? "))
  62.     forall_nodes(v,G)
  63.      { forall_nodes(w,G) cout << string("%6d ",Mi(v,w));
  64.        newline;
  65.        }
  66.   newline;
  67. }
  68.  
  69.  
  70. edge_array<double> cost2(G,0);
  71. node_array<double> dist3(G,0);
  72. node_array<double> dist4(G,0);
  73.  
  74. forall_edges(e,G) cost2[e] = cost1[e];
  75.  
  76. cout << "DIJKSTRA <double>     ";
  77. cout.flush();
  78. DIJKSTRA(G,s,cost2,dist3,pred);
  79. cout << string("%6.2f sec  \n",used_time(T));
  80.  
  81.  
  82. cout << "BELLMAN_FORD <double> ";
  83. cout.flush();
  84. BELLMAN_FORD(G,s,cost2,dist4,pred);
  85. cout << string("%6.2f sec  \n",used_time(T));
  86.  
  87.  
  88. if (Yes("output ? "))
  89.  { forall_nodes(v,G)
  90.    { G.print_node(v);
  91.      cout << "  " << dist3[v] << "  " << dist4[v];
  92.      newline;
  93.     }
  94.    newline;
  95.   }
  96.  
  97. if (Yes("all pairs shortest paths <double> ? "))
  98. { 
  99.   node_matrix<double> Mr(G);
  100.  
  101.   used_time(T);
  102.   cout << "ALL PAIRS SHORTEST PATHS <double>  ";
  103.   cout.flush();
  104.   ALL_PAIRS_SHORTEST_PATHS(G,cost2,Mr);
  105.   cout << string("%.2f sec\n",used_time(T));
  106.   
  107.   if (Yes("output ? "))
  108.     forall_nodes(v,G)
  109.      { forall_nodes(w,G) cout << string("%6.2f ",Mr(v,w));
  110.        newline;
  111.        }
  112.   newline;
  113.  
  114.  }
  115.  
  116.   return 0;
  117. }
  118.